package a_doubleWrite;

import java.util.Deque;
import java.util.LinkedList;

/**
 32. 最长有效括号
 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

 示例 1：
 输入：s = "(()"
 输出：2
 解释：最长有效括号子串是 "()"
 * @author: luolidong
 * @create: 2021-07-17 11:48
 * @version: 1.0
 */
public class L32 {
    //(())()
    public int longestValidParentheses(String s) {
        if(s==null||s.length()<2) return 0;

        Deque<Integer> stack=new LinkedList<>();
        stack.push(-1);
        //遍历字符串
        int maxLen=0;
        int i=0;
        while (i<s.length()){
            char c=s.charAt(i);
            if(c=='('){
                stack.push(i);
            }else {
                //如果是），先弹出
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }else {
                    maxLen=Math.max(maxLen, i-stack.peek());
                }
            }
            i++;
        }
        return maxLen;
    }

    public int longestValidParentheses1(String s) {
        if(s.length()<2) return 0;
        int left=0,right=0,max=0;
        //从左往右，如果left==right，计算最大值
        for (int i = 0; i <s.length() ; i++) {
            if(s.charAt(i)=='(') left++;
            if(s.charAt(i)==')') right++;
            if(left==right){
                max=Math.max(left*2,max);
            }else if(right>left){//)多与（
                right=left=0;
            }
        }
        //从右往左，如果left==right，计算最大值
        for (int i = s.length()-1; i >=0 ; i--) {
            if(s.charAt(i)=='(') left++;
            if(s.charAt(i)==')') right++;
            if(left==right){
                max=Math.max(left*2,max);
            }else if(left>right){//（多于）
                right=left=0;
            }
        }
        return max;
    }
}
